package com.github.hgkmail.hello.leetcode101.dp.twod;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;

import java.util.Arrays;

//二维(two-d)数组动态规划
//dp[i][j]：以点(i,j)结尾，包含点(i,j)的最小数字和
//dp[i][j] = max{ dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j] }
public class LC64MinimumPathSum {
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        if (m<=0) {
            return 0;
        }
        int n=grid[0].length;
        if (n<=0) {
            return 0;
        }
        int[][] dp=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i==0 && j==0) { //起点
                    dp[i][j] = grid[i][j];
                    continue;
                }
                if (i<=0) { //只能往左退
                    dp[i][j]=dp[i][j-1]+grid[i][j];
                    continue;
                }
                if (j<=0) { //只能往上退
                    dp[i][j]=dp[i-1][j]+grid[i][j];
                    continue;
                }
                dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j]; //这里可以最大也可以最小
            }
        }
        return dp[m-1][n-1];
    }
    public static void main(String[] args) {
        int[][] grid=CommonUtil.parseLc2DArray("[[1,3,1],[1,5,1],[4,2,1]]");
        System.out.println(new LC64MinimumPathSum().minPathSum(grid));
    }
}
